#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *longestCommonPrefix(char **strs, int strsSize)
{
    if (strsSize == 0)
    { // 边界情况：空数组
        return "";
    }

    char *prefix = strs[0]; // 使用第一个字符串作为基准
    for (int i = 1; i < strsSize; ++i)
    {
        // 逐字符比较
        int j = 0;
        while (strs[i][j] != '\0' && prefix[j] != '\0' && strs[i][j] == prefix[j])
        {
            j++;
        }
        // 更新最长公共前缀
        prefix = (char *)realloc(prefix, j + 1); // 重新分配内存以匹配新的前缀长度
        if (prefix == NULL)
        {                // 如果内存分配失败
            return NULL; // 或者可以根据实际情况抛出错误
        }
        prefix[j] = '\0'; // 确保字符串以 '\0' 结尾
        if (j == 0)
        { // 如果没有公共前缀
            return "";
        }
    }
    return prefix;
}

int main()
{
    char *strs[] = {"flower", "flow", "flight"};
    int strsSize = sizeof(strs) / sizeof(strs[0]);

    char *result = longestCommonPrefix(strs, strsSize);
    printf("The longest common prefix is: %s\n", result);

    // 注意：在实际应用中，应该释放由 longestCommonPrefix 分配的内存
    free(result);

    return 0;
}
char *longestCommonPrefix(char **strs, int strsSize)
{
    if (strsSize == 0)
    {
        return "";
    }
    char *prefix = strs[0];
    for (int i = 1; i < strsSize; ++i)
    {

        int j = 0;
        while (strs[i][j] != '\0' && prefix[j] != '\0' && strs[i][j] == prefix[j])
        {
            j++;
        }
        prefix = (char *)realloc(prefix, j + 1);
        if (prefix == NULL)
        {
            return NULL;
        }
        prefix[j] = '\0';
        if (j == 0)
        {
            return "";
        }
    }
    return prefix;
}